package com.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 三数之和
 */
public class ThreeSum {

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        int start;
        int end;
        int length = nums.length;
        for (int i = 0; i <= length-2; i++) {
            if (i!=0&&nums[i]==nums[i-1]){
                continue;
            }
            start=i+1;
            end=nums.length-1;
            while (start<end){
                if (nums[i]+nums[start]+nums[end]==0){
                    List<Integer> arrList=new ArrayList<Integer>();
                    arrList.add(nums[i]);
                    arrList.add(nums[start]);
                    arrList.add(nums[end]);
                    list.add(arrList);
                    start++;
                    end--;
                    while (start<end&&nums[start]==nums[start-1]){
                        start++;
                    }
                    while (start<end&&nums[end]==nums[end+1]){
                        end--;
                    }
                }else if(nums[i]+nums[start]+nums[end]<0){
                    start++;
                }else {
                    end--;
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
//        int[] nums = {-1, 0, 1, 2, -1, -4};
        int[] nums = {0,0,0,0,};
        System.out.println(threeSum(nums));
    }


}
